// 稳定 时间O(N*2) 空间O(1)
function insertionSort(arr) {
    for(let i = 1; i < arr.length; i++) {
        let key = arr[i]
        let j = i - 1
        while(j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
    return arr
}
let arr = [9, 4, 2, 1]
console.log(insertionSort(arr));